#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "Scanner.h"
#include "../BMC.h"
#include "../BMCRepository.h"
#include "../../NESMemory.h"
#include "../../6502.h"
#include "../../List.h"
#include "../../Statistics.h"

static uint8_t Hardspots[0x10000];

extern const InstructionData Instructions[256];

extern Statistics* ExecutionStatistics;

void SCN_Init(){
    memset(Hardspots, 0, 0x10000 * sizeof(uint8_t));
    BMCRInit();
}

//This function is the heart of the scanner. It builds an entire BMC
//and calls itself recursively in order to build soft-spot BMC's
static BMC* ScanBMC(uint16_t Addr, BMCList* List, uint32_t BMCDepth){
    uint8_t Opcode;
    uint16_t PC, TargetAddr;
    BMCInstruction* NewInstr;
    BMC* Block, *TargetBlock;
    uint32_t InitialSet, IsBranch;
    
    InitialSet = 0;
    IsBranch = 0;
    
    PC = Addr;
    
    if(BMCDepth >= 2){
        return NULL;
    }

    Block = BMCNew(Addr);
    
    Opcode = ReadMemory(PC);
    
    //Is it time to finalize the current BMC?
    while( !(Instructions[Opcode].ScanData & SDE_HARDSPOT) && !Hardspots[PC] ){
        
        //Set the initial BMC address as a hard spot
        if(!InitialSet)
            Hardspots[Addr] = 1, InitialSet = 1;        
        
        //is the current instruction a branch?
        if(Instructions[Opcode].ScanData & SDE_SOFTSPOT){
            //Calculate TargetAddr
            uint8_t Offset;
            int16_t Disp;
            Offset = ReadMemory(PC+1);
            Disp = (int8_t) Offset;
            TargetAddr = PC + Instructions[Opcode].Size + Disp;
            
            //Save current BMC to the repository. This is needed, since
            //the branch target may be inside this BMC or it may be the one
            //preceding the current one. This ensures that no two distinct
            //BMC's overlap.
            BMCRRefresh(Block, 0);            
            
            IsBranch = 1;
            
            TargetBlock = BMCRSearch(TargetAddr);
            
            //Have we generated the code for the target yet?
            if(TargetBlock){
                //If so, it is necessary to update the instruction map for the 
                //target BMC
                BMCAddEntryPoint(TargetBlock, TargetAddr);
                
                //Mark the target BMC to be reanalyzed
                LST_Enqueue(List->AnalyzeBlocks, TargetBlock);
            }
            else{
                //Otherwise, we should recursively generate code for the target
                BMC* TargetBMC;
                
                TargetBMC = ScanBMC(TargetAddr, List, BMCDepth + 1);
                
                if(TargetBMC)
                    BMCLAdd(List, TargetBMC);
            }
        }
        //Create an instruction representation for the current instruction
        NewInstr = BMCINew(PC, Opcode, Instructions[Opcode].Size, IsBranch ? BMCIT_Branch : BMCIT_Other, ReadMemory(PC+1), ReadMemory(PC+2));
        
        if(IsBranch)
            NewInstr->InstructionInformation.BranchInfo = BMCBIFNew(TargetAddr, 0);
        
        BMCAddInstruction(Block, NewInstr);
        //PC += Instructions[Opcode].Size;
        
        PC += CPUGetInstructionSize(Opcode);
        
        Block->BlockSize += CPUGetInstructionSize(Opcode);      
        
        Opcode = ReadMemory(PC);
        IsBranch = 0;
    }
        
    //Check whether BMC scanning stopped because it hit a PC hardspot
    if(!Hardspots[PC]){
        //If NOT, the last instruction must be placed inside last BMC
        
        //Add the last instruction into the BMC
        NewInstr = BMCINew(PC, Opcode, Instructions[Opcode].Size, BMCIT_Jump, ReadMemory(PC+1), ReadMemory(PC+2));
        BMCAddInstruction(Block, NewInstr); 
        Block->BlockSize += CPUGetInstructionSize(Opcode);  
        
        //This is only true when the target instruction is
        //already a jump instruction. Many games, such as 
        //Super Mario Bros use Jump Tables extensively.
        //Set the initial BMC address as a hard spot
        if(!InitialSet)
            Hardspots[Addr] = 1, InitialSet = 1;              
    }
    
    //Make sure the BMC is correctly placed into the repository
    BMCRRefresh(Block, 1);
    
    //Insert the current BMC into the BMC List
    return Block;
}

void SCN_BMCAnalysis(BMC* Block){
    
    uint32_t i, Dirty, CycleCount;
    uint16_t BlockStart, BlockEnd, Target;
    
    if(!Block)
        return;
    
    CycleCount = 0;
    Target = 0;
    Dirty = 0;
    
    BlockStart = Block->StartAddr;
    BlockEnd = BlockStart + Block->BlockSize;
    
    for(i = 0; i < Block->Length; i++){
        CycleCount += Instructions[Block->Instructions[i]->Opcode].OpCycles;
        
        if(Block->Instructions[i]->InstructionType == BMCIT_Branch){
            Dirty = 1;
            Target = Block->Instructions[i]->InstructionInformation.BranchInfo->Target;
            if((Target >= BlockStart) && (Target < BlockEnd))
                Block->Instructions[i]->InstructionInformation.BranchInfo->BranchFlags |= BMCBI_TargetInSameBMC;
        }
    }
    
    for(i = BlockStart; i < BlockEnd; i++)
        Dirty += BMCSearchEntryPoint(Block, i);
    
    //If block is dirty, mark it as pure.
    Block->Pure = Dirty ? 0 : 1;
    
    if(!Dirty)
        Block->Cycles = CycleCount;
    
}

static void SCN_CopyEntryPoints(uint16_t Data, void* Args){
    BMCEPInsert(((BMC*)Args)->EntryPoints, Data, 1);
}

static void SCN_CoalesceBlocks(BMC* First, BMC* Last){
    uint32_t i;
    //Merge Instructions
    for(i = 0; i < Last->Length; i++)
        BMCAddInstruction(First, Last->Instructions[i]);
    
    //printf("\n\nfirst [0x%04X] (%p)\n", First->StartAddr, First);
    //BMCEPDump(First);
    
    //printf("\n\nlast [0x%04X] (%p)\n", Last->StartAddr, Last);
    //BMCEPDump(Last);
    
    //Merge Entry Points
    BMCEPExecute(Last, SCN_CopyEntryPoints, First);
    
    //printf("final [0x%04X] (%p)\n",First->StartAddr, First);
    //BMCEPDump(First);    
    
    First->BlockSize += Last->BlockSize;
    First->Pure = (First->Pure && Last->Pure) ? 1 : 0;
    
    if(First->Pure)
        First->Cycles += Last->Cycles;
    else
        First->Cycles = 0;
    
    BMCRRefresh(First, 1);
    
    free(Last);
}

//Implements the Block Coalescing BMC optimization. This optimization tries
//to recognize all adjacent blocks in the list and then combining them together
void SCN_BlockCoalescing(BMCList* BlockList){
    uint32_t i, j, NB;
    uint32_t Done = 0;
    BMC* BlockI, *BlockJ;
    
    NB = BMCLNumBlocks(BlockList);
    
    if(NB == 1)
        return;
    
    //printf("BLOCK COALESCING CALL\n\n");
    
    while(!Done){
        
        Done = 1;        
        
        for(i = 0; i < NB ; i++){
            BlockI = BlockList->Blocks[i];
            
            if(!BlockI)
                continue;
            
            for(j = ((i + 1) % NB); j != i; j = ((j + 1) % NB)){
                BlockJ = BlockList->Blocks[j];
                
                if(!BlockJ)
                    continue;
                
                if((BlockI->StartAddr + BlockI->BlockSize) == BlockJ->StartAddr){
                    //Coalesce!
                    Done = 0;
                    SCN_CoalesceBlocks(BlockI, BlockJ);
                    while(LST_Remove(BlockList->AnalyzeBlocks, BlockJ));
                    BlockList->Blocks[j] = NULL;
                    ExecutionStatistics->DBT_BC_CoalescingOps++;
                }
            }
        }
        
    }
}

//This function is actually a frontend for the scanning engine.
//It creates the BMCList, calls ScanBMC for the starting address and
//returns the final BMCList
BMCList* SCN_Scan(uint16_t StartingAddress){
    BMCList *BlockList;
    BlockList = BMCLNew();
    
    BMCLAdd(BlockList, ScanBMC(StartingAddress, BlockList, 0));
    
    return BlockList;
}
